package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 236. 二叉树的最近公共祖先
 * 剑指 Offer 68 - II. 二叉树的最近公共祖先
 * 面试题 04.08. 首个共同祖先
 *
 * @Author liw
 * @Date 2021/5/8 11:51
 * @Version 1.0
 */
public class LowestCommonAncestor2 {

    public static void main(String[] args) {
        LowestCommonAncestor2 test = new LowestCommonAncestor2();
        List<TreeNode> list = new ArrayList<>();
        TreeNode treeNode = test.lowestCommonAncestor(TreeNode.getInstance(), new TreeNode(2), new TreeNode(3));
        System.out.println(treeNode.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val == q.val) {
            return p;
        }
        List<TreeNode> l1 = new ArrayList<>();
        find(root, p, l1);
        List<TreeNode> l2 = new ArrayList<>();
        find(root, q, l2);
        int size = Math.min(l1.size(), l2.size());
        TreeNode item = l1.get(0);
        for (int i = 0; i < size; i++) {
            TreeNode t1 = l1.get(i);
            TreeNode t2 = l2.get(i);
            if (t1.val != t2.val) {
                return item;
            }
            item = t1;
        }
        return item;
    }

    private boolean find(TreeNode node, TreeNode value, List<TreeNode> list) {
        if (node == null) {
            return false;
        }
        list.add(node);
        if (node.val == value.val) {
            return true;
        }
        boolean b = find(node.left, value, list);
        if (b) {
            return true;
        }
        b = find(node.right, value, list);
        if (b) {
            return true;
        }
        list.remove(list.size() - 1);
        return false;
    }

}
